import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-06-07
 * Time: 21:34
 */

public class BinaryTree {
    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char ch) {
            this.val = ch;
        }
    }

    public TreeNode root;

    public TreeNode create() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }

    // 前序遍历   根 -> 左 -> 右
    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历   左 -> 根 -> 右
    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后序遍历    左  -> 右 -> 根
    void postOrde(TreeNode root) {
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val + " ");
    }

    /**
     * 层序遍历
     * //方法一 : 创建一个队列, 先将根节点放入对列 , 当对列不为空时,弹出对列的顶元素
     * // 打印弹出的元素,将该元素的子节点存入对列中,直到队列为空
     */
    void levelOrder1(TreeNode root) {
        if (root == null) {
            return;
        }
        //创建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        //根节点插入对列
        queue.offer(root);
        //当对列不为空,继续循环
        while (!queue.isEmpty()) {
            //弹出元素并打印
            TreeNode ret = queue.poll();
            System.out.print(ret.val + " ");
            //将弹出的节点的孩子节点插入对列
            if (ret.left != null) {
                queue.offer(ret.left);
            }
            if (ret.right != null) queue.offer(ret.right);
        }
    }

    //方法二: 在方法一的基础上改进, 返回一个二维的顺序表,表中每一行存放 二叉树每一层的值
    List<List<Character>> levelOrder2(TreeNode root) {
        //创建二维的顺序表
        List<List<Character>> ret = new ArrayList<>();
        if (root == null) return null;
        //创建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        //根节点插入对列
        queue.offer(root);
        while (!queue.isEmpty()) {
            //创建一维的顺序表
            List<Character> list = new ArrayList<>();
            //定义size ,获取当前对列中数值的数量
            int size = queue.size();
            //每次弹出size个元素 ,并存放到顺序表中
            while (size != 0) {
                //弹出元素
                TreeNode cur = queue.poll();
                //每弹出一个元素 size-1
                size--;
                //将弹出的元素放入顺序表
                list.add(cur.val);
                //将cur 的子节点加入对列
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            //将顺序表添加到二维的顺序表中
            ret.add(list);
        }
        return ret;
    }

    int NodeSize = 0;

    //统计二叉树中 节点的个数(1 . 遍历思路)
    void size(TreeNode root) {
        if (root == null) {
            return;
        }
        ;
        NodeSize++;
        size(root.left);
        size(root.right);
    }

    int leafNode = 0;

    /**
     * 计算二叉树中叶子节点的个数
     */
    //方法一 : 遍历查找
    void getLeafNode1(TreeNode root) {

        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafNode++;
            return;
        }
        getLeafNode1(root.left);
        getLeafNode1(root.right);
    }

    //方法二: 分解为子问题
    int getLeafNode2(TreeNode root) {

        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNode2(root.left) + getLeafNode2(root.right);
    }

    /**
     * 获取第k层节点的个数
     * 思路 :要求 第K层节点的个数 相当于求 左子树和右子树的第k-1层各有多少个节点,之后相加,
     * K 相当于整个二叉树的第K层 , 相当于左子树的第K-1才能 ,相当于左子树的左子树的第 k-2层
     * 直到 当 K相当于 左边子树的第 1 层, 即 k=1 时, 说明找到了 1 个整个二叉树的第K层的节点.
     * 以此类推 , 找到所有节点
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        //当k=1时返回 1 ,说明找到一个节点
        if (k == 1) {
            return 1;
        }
        //先递归左子树,再递归右子树,最后相加求得结果
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    /**
     * 计算树的高度
     * 思路 : 二叉树的高度 = 左右子树高度的最大值 + 1
     * 分别计算每颗子树的高度,取最大值
     * 左子树的高度最大值
     * 时间复杂度: O(n)  因为需要遍历到每一个节点计算高度
     */
    int getTreeHight(TreeNode root) {
        //递归到root==null,返回0,说明这棵树的左(右)分支递归结束
        if (root == null) {
            return 0;
        }
        //分别记录其最大值
        int left = getTreeHight(root.left);
        int right = getTreeHight(root.right);
        //返回最大值+1
        return left > right ? left + 1 : right + 1;

    }

    /**
     * 在二叉树中查找 值为value的值
     */
    TreeNode findVaule(TreeNode root, char val) {
        if (root == null) return null;
        if (root.val == val) {
            return root;
        }
        //递归查找左子树有无要查找的值,有返回这个节点
        TreeNode ret = findVaule(root.left, val);
        if (ret != null) {
            return ret;
        }
        //递归查找左子树有无要查找的值,有返回这个节点
        ret = findVaule(root.right, val);
        if (ret != null) {
            return ret;
        }
        //走到这说明左右子树都没有,返回null
        return null;
    }

    //判断是否为完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) return false;
        //创建一个队列,放入根节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //只要队列不为空 , 就一直弹出元素
        while (!queue.isEmpty()) {
            //弹出栈顶元素
            TreeNode cur = queue.poll();
            //只要cur不为空,将cur的孩子节点存入队列 ,为空说明已经遇到了一个null,跳出循环
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        //代码走到这,说明遇到cur为 null了 , 此时遍历队列, 队列中如果全为null,说明为完全二叉树,只要有一个不为null,说明不是完全二叉树
        while (!queue.isEmpty()) {
            if (queue.peek() != null) {
                return false;
            } else {
                queue.poll();
            }
        }
        return true;
    }

    /*求二叉树的两个节点p q 的最近公共祖先
    方法一:
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if( root == null) return null;
        if( p == root || q== root) return root;
        //走到这里说明p.q都不与root相等 , 分别递归 root 的左边和右边
        TreeNode left = lowestCommonAncestor( root.left, p, q);
        TreeNode right = lowestCommonAncestor( root.right, p, q);
        //当两边都找到和根相等 ,就说明 root 为公共祖先
        if( left != null && right != null) {
            return root;
        }
        //左边找到
        else if( left != null) {
            return left;
        } else if( right !=null) { //右边找到
            return right;
        }
        return null;
    }
     //方法二 : 利用两个栈,分别存放从根到p , q节点的所有值, 再从较大的栈顶弹出两个栈大小的差值个元素.//而后比较两个栈中的所有元素 , 若相等,则该元素就为公共祖先
class Solution {
    private boolean getPath( TreeNode root, TreeNode p , Stack<TreeNode> stack) {
         if( root == null || p== null) return false;
         stack.push(root);
         //当root 遇到p 时说明路径结束
        if( root == p) return true;
        boolean flag1 = getPath( root.left ,p,stack);
        if( flag1 == true) return true;
        boolean flag2 = getPath( root.right,p,stack);
        if( flag2 == true) return true;
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        if( getPath(root ,p ,s1) && getPath(root, q,s2)) {
            while( s1.size() > s2.size()) {
                s1.pop();
            }
            while( s1.size() < s2.size()) {
                s2.pop();
            }
            while(!s1.isEmpty() && !s2.isEmpty()) {
                if( s1.peek() == s2.peek()) {
                    return s1.pop();
                } else {
                     s1.pop();
                     s2.pop();
                }
            }
        }
        return null;
    }
}*/
    //判断平衡二叉树
    //求这个树的高度
    public int height(TreeNode root) {
        if (root == null) return 0;
        int left = height(root.left);
        int right = height(root.right);
        //在求高度的过程中同时判断,左右子树的高度差 ,如果中间过程,高度差>1了,说明就不是高度平衡的二叉树了 ,返回 -1. 此处只要出现了left 或者 right =-1的情况就说明不是平衡二叉树了 ,返回-1
        if (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
            return left > right ? left + 1 : right + 1;
        } else {
            return -1;
        }

    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return height(root) >= 0;
    }

    /**
     * 根据二叉树创建字符串
     * 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
     * <p>
     * 空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/construct-string-from-binary-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    class Solution1 {
        StringBuilder str = new StringBuilder();

        public void tree2strChild(TreeNode root) {
            if (root == null) return;
            str.append(root.val);
            if (root.left != null) {
                str.append("(");
                tree2strChild(root.left);
                str.append(")");
            } else {
                if (root.right == null) {
                    return;
                } else {
                    str.append("()");
                }
            }
            if (root.right != null) {
                str.append("(");
                tree2strChild(root.right);
                str.append(")");
            } else {
                return;
            }
        }

        public String tree2str(TreeNode root) {
            if (root == null) return null;
            tree2strChild(root);
            return str.toString();
        }
    }

    /**
     * 06. 从中序与后序遍历序列构造二叉树
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     */
    class Solution2 {
        int pi;

        public TreeNode buildTreeChild(int[] inorder, int[] postorder, int ib, int ie) {
            if (ib > ie) return null;
            TreeNode root = new TreeNode(postorder[pi]);
            int ret = findIndex(postorder[pi], inorder, ib, ie);
            pi--;
            root.right = buildTreeChild(inorder, postorder, ret + 1, ie);
            root.left = buildTreeChild(inorder, postorder, ib, ret - 1);
            return root;
        }

        int findIndex(int val, int[] inorder, int ib, int ie) {
            for (int i = ib; i <= ie; i++) {
                if (inorder[i] == val) {
                    return i;
                }
            }
            return -1;
        }

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            pi = postorder.length - 1;
            return buildTreeChild(inorder, postorder, 0, inorder.length - 1);
        }
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     */
    class Solution3 {
        int pi = 0;

        public TreeNode buildTreeChild(int[] preorder, int[] inorder, int ib, int ie) {
            if (ib > ie) return null;
            TreeNode head = new TreeNode(preorder[pi]);
            int retIndex = findIndex(preorder[pi], inorder, ib, ie);
            pi++;
            head.left = buildTreeChild(preorder, inorder, ib, retIndex - 1);
            head.right = buildTreeChild(preorder, inorder, retIndex + 1, ie);
            return head;
        }

        public int findIndex(int val, int[] inorder, int ib, int ie) {
            for (int i = ib; i <= ie; i++) {
                if (inorder[i] == val) {
                    return i;
                }
            }
            return -1;
        }

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChild(preorder, inorder, 0, inorder.length - 1);

        }
    }
    /**
     * 6. 二叉树的最近公共祖先
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     *
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
     * ”*/
    class Solution4 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if( root == null) return null;
            if( p == root || q==root ) return root;
            TreeNode left = lowestCommonAncestor( root.left , p ,q);
            TreeNode right = lowestCommonAncestor( root.right , p ,q);
            if( left!=null && right!=null) {
                return root;
            } else if( left !=null ) {
                return left;
            } else if( right != null) {
                return right;
            }
            return null;

        }
    }

    /**
     * 二叉树的完全性检验
     * 给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
     *
     * 在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。
     */
    class Solution45{

        public boolean isCompleteTree(TreeNode root) {
            if( root == null) return false;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode cur = root;
            while(cur!=null ) {
                cur = queue.poll();
                if( cur!=null )queue.offer(cur.left);
                if( cur!=null )queue.offer(cur.right);
            }
            while( !queue.isEmpty()) {
                if( queue.poll()!=null) {
                    return false;
                }
            }
            return true;

        }
    }

    /**
     * 958. 二叉树的完全性检验
     * 给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
     *
     * 在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。
     * */
    class Solution{
        //判断两个树是否相同
        public boolean isSameTree( TreeNode root1 , TreeNode root2) {
            if( root1 == null &&  root2 == null)  return true;
            if( root1 == null && root2!=null || root1 != null && root2 == null ) return false;
            if( root1.val != root2.val) return false;
            return isSameTree( root1.left ,root2.left) && isSameTree( root1.right , root2.right);
        }

        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if( root == null) return false;
            //判断根是否相同
            if( isSameTree( root , subRoot) ) return true;
            //判断左边是否有子树
            if( isSubtree( root.left , subRoot)) return true;
            //判断右边是否有子树
            if( isSubtree( root.right , subRoot)) return true;
            return false;
        }
    }

    /**
     * 617. 合并二叉树
     * 给你两棵二叉树： root1 和 root2 。
     *
     * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
     *
     * 返回合并后的二叉树。
     *
     * 注意: 合并过程必须从两个树的根节点开始。
     */
    class Solution7 {
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            //if( root1 == null && root2 == null ) return null;
            //当 root为空返回 root2
            if( root1 == null){
                return root2;
            }
            //root2 为空返回 root1
            if( root2 == null){
                return root1;
            }
            root1.val = root1.val + root2.val;
            //递归左子树
            root1.left = mergeTrees( root1.left , root2.left);
            //递归右子树
            root1.right = mergeTrees( root1.right , root2.right);
            return root1;
        }
    }

    /**
     * . 相同的树
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     *
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     */
    class Solution8 {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            //如果两棵树都为空 , 返回true
            if( p==null && q==null) return true;
            //一个为空 一个不为空 ,说明结构不同,返回false
            if( p==null && q!=null || p!=null && q==null) return false;
            //如果节点值不相同返回false
            if( p.val != q.val ) return false;
            //如果左右树都相同,返回true
            return isSameTree( p.left ,q.left) && isSameTree( p.right,q.right);
        }
    }

    /**
     * . 二叉树的层序遍历
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     */
    class Solution9 {
        public List<List<Integer>> levelOrder(TreeNode root) {
            //创建二维的顺序表
            List<List<Integer>> ret = new ArrayList<>();
            if( root == null) {
                return ret;
            }

            //创建一个队列
            Queue<TreeNode> queue = new LinkedList<>();
            //根节点插入对列
            queue.offer(root);
            while(!queue.isEmpty()) {
                //创建一维的顺序表
                List<Integer> list = new ArrayList<>();
                //定义size ,获取当前对列中数值的数量
                int size = queue.size();
                //每次弹出size个元素 ,并存放到顺序表中
                while( size!=0 ) {
                    //弹出元素
                    TreeNode cur = queue.poll();
                    //每弹出一个元素 size-1
                    size--;
                    //将弹出的元素放入顺序表
                    list.add(cur.val);
                    //将cur 的子节点加入对列
                    if( cur.left != null)  queue.offer(cur.left);
                    if( cur.right !=null)  queue.offer(cur.right);
                }
                //将顺序表添加到二维的顺序表中
                ret.add(list);
            }
            return ret;
        }
    }

    /**
     * . 二维网格迁移
     * 给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
     *
     * 每次「迁移」操作将会引发下述活动：
     *
     * 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
     * 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
     * 位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
     * 请你返回 k 次迁移操作后最终得到的 二维网格。
     */
    class Solution10 {
        public List<List<Integer>> shiftGrid(int[][] grid, int k) {
            int m = grid.length, n = grid[0].length;
            int[] arr = new int[m * n]; //按迁移k次后的新位置存储grid的所有元素到一维数组arr
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    arr[(i * n + j + k) % (m * n)] = grid[i][j];
                }
            }
            List<List<Integer>> ans = new ArrayList<>();
            int index = 0;
            for (int i = 0; i < m; i++) { //将一维数组展开成二维数组
                List<Integer> path = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    path.add(arr[index++]);
                }
                ans.add(path);
            }
            return ans;
        }
    }
    /**
     * 二叉树的层序遍历 ,从最后一层,从左往右,自下往上遍历
     * */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List< List<Integer>> ret = new  ArrayList<>();
        if( root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while( !queue.isEmpty()) {
            int  size = queue.size();
            List<Integer> list = new   ArrayList<>();
            while( size != 0) {
                TreeNode cur = queue.poll();
                size--;
                list.add(cur.val);
                if( cur.left!=null) queue.offer(cur.left);
                if( cur.right!=null) queue.offer(cur.right);
            }
            ret.add(0,list);
        }
        return ret;
    }

    /**
     * 从前序与中序遍历序列构造二叉树
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     * 解题思路 : 模拟使用前序遍历和中序遍历构建二叉树的过程, 定义pi从 0开始遍历 前序遍历的数组, left  和 right 分别为中序遍历数组的两端,每次递归都
     *        拿当前pre中对应的的数去遍历查找在inorder数组中的当前位置, 从该位置进行二分,直到left >right,停止,二叉树构建完毕
     */
    class Solution13 {
        int pi = 0;
        public TreeNode buildTreeChild( int []preorder ,int[] inorder ,int left ,int right) {
            if( left > right) return null;
            TreeNode root = new TreeNode( preorder[pi]);
            int ret = findIndex( preorder[pi], inorder, left ,right);
            pi++;
            root.left = buildTreeChild( preorder,inorder,left,ret-1);
            root.right = buildTreeChild( preorder,inorder,ret+1,right);
            return root;
        }

        public int findIndex( int key, int[] inorder,int left ,int right) {
            for( int i=left; i<=right; i++) {
                if( inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChild( preorder, inorder, 0, inorder.length-1);
        }
    }

    /**
     * 106. 从中序与后序遍历序列构造二叉树
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     *
     */
    class Solution {
        int pi;
        public TreeNode buildTreeChild( int[] inorder, int[] postorder ,int ib,int ie) {
            if( ib > ie) return null;
            TreeNode root = new TreeNode( postorder[pi]);
            int ret = findIndex( postorder[pi],inorder,ib,ie);
            pi--;
            root.right = buildTreeChild( inorder ,postorder , ret+1 ,ie);
            root.left = buildTreeChild( inorder ,postorder , ib ,ret-1);
            return root;
        }
        int findIndex(int val,int[] inorder,int ib,int ie) {
            for(int i=ib;i<=ie;i++) {
                if( inorder[i] == val) {
                    return i;
                }
            }
            return -1;
        }
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            pi = postorder.length-1;
            return buildTreeChild( inorder,postorder,0,inorder.length-1);
        }
    }
}



